package arithmetic.leetCode;

import java.util.Random;

/**
 * 快速选择
 * 快速选择算法 的平均时间复杂度为 {O}(N)O(N)。就像快速排序那样，本算法也是 Tony Hoare 发明的，因此也被称为 Hoare选择算法。
 * <p>
 * 本方法大致上与快速排序相同。简便起见，注意到第 k 个最大元素也就是第 N - k 个最小元素，因此可以用第 k 小算法来解决本问题。
 * <p>
 * 首先，我们选择一个枢轴，并在线性时间内定义其在排序数组中的位置。这可以通过 划分算法 的帮助来完成。
 * <p>
 * 为了实现划分，沿着数组移动，将每个元素与枢轴进行比较，并将小于枢轴的所有元素移动到枢轴的左侧。
 * <p>
 * 这样，在输出的数组中，枢轴达到其合适位置。所有小于枢轴的元素都在其左侧，所有大于或等于的元素都在其右侧。
 * <p>
 * 这样，数组就被分成了两部分。如果是快速排序算法，会在这里递归地对两部分进行快速排序，时间复杂度为 {O}(N \log N)O(NlogN)。
 * <p>
 * 而在这里，由于知道要找的第 N - k 小的元素在哪部分中，我们不需要对两部分都做处理，这样就将平均时间复杂度下降到 {O}(N)O(N)。
 * <p>
 * 最终的算法十分直接了当 :
 * <p>
 * 随机选择一个枢轴。
 * <p>
 * 使用划分算法将枢轴放在数组中的合适位置 pos。将小于枢轴的元素移到左边，大于等于枢轴的元素移到右边。
 * <p>
 * 比较 pos 和 N - k 以决定在哪边继续递归处理。
 * <p>
 * ! 注意，本算法也适用于有重复的数组
 * <p>
 * 作者：LeetCode
 * 链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author dycong
 * @date 2019/11/18 19:02
 */
public class FindKthLargest_215_2 {
    public static void main(String[] args) {
        FindKthLargest_215_2 findKthLargest_215 = new FindKthLargest_215_2();
        int[] nums = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        System.out.println(findKthLargest_215.findKthLargest_fast(nums, 4));
    }

    Random random = new Random();

    public int findKthLargest_fast(int[] nums, int k) {
        return quickselect(nums, 0, nums.length - 1, nums.length - k);
    }

    /**
     * 简便起见，注意到第 k 个最大元素也就是第 N - k 个最小元素，因此可以用第 k 小算法来解决本问题。
     *
     * @param nums
     * @param left
     * @param right
     * @param k_smallest
     * @return
     */
    public int quickselect(int[] nums, int left, int right, int k_smallest) {
        if (left == right) // If the list contains only one element,
            return nums[left];  // return that element
        int pivot_index = left + random.nextInt(right - left);

        pivot_index = partition(nums, left, right, pivot_index);

        if (pivot_index == k_smallest) {
            return nums[pivot_index];
        }
        if (k_smallest < pivot_index) {
            //pivot_index - 1
            return quickselect(nums, left, pivot_index - 1, k_smallest);
        }
        //pivot_index + 1
        return quickselect(nums, pivot_index + 1, right, k_smallest);
    }

    public int partition(int[] nums, int left, int right, int pivot_index) {
        // 1. move pivot to end
        swap(nums, pivot_index, right);
        int store_index = left;
        // 2. move all smaller elements to the left
        for (int i = left; i < right; i++) {
            if (nums[i] < nums[right]) {
                if (store_index != i) {
                    swap(nums, store_index, i);
                }
                store_index++;
            }
        }

        // 3. move pivot to its final place
        swap(nums, store_index, right);
        return store_index;
    }


    public void swap(int[] nums, int a, int b) {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }


}
